package cn.cxq.learning.tree;

/**
 * 二叉树
 */
public class BinaryTree {

    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void preorderTraversal() {
        if (this.root != null) this.root.preorderTraversal();
        else System.out.println("二叉树为空~~~");
    }

    public void inorderTraversal() {
        if (this.root != null) this.root.inorderTraversal();
        else System.out.println("二叉树为空~~~");
    }

    public void postorderTraversal() {
        if (this.root != null) this.root.postorderTraversal();
        else System.out.println("二叉树为空~~~");
    }

    public Node preorderSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空~~~");
            return null;
        } else {
            Node node = root.preorderSearch(no);
            if (node == null) {
                System.out.println("未找到该节点");
                return null;
            } else {
                System.out.println(node);
                return node;
            }
        }
    }

    public Node inorderSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空~~~");
            return null;
        } else {
            Node node = root.inorderSearch(no);
            if (node == null) {
                System.out.println("未找到该节点");
                return null;
            } else {
                System.out.println(node);
                return node;
            }
        }
    }

    public Node postorderSearch(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空~~~");
            return null;
        } else {
            Node node = root.postorderSearch(no);
            if (node == null) {
                System.out.println("未找到该节点");
                return null;
            } else {
                System.out.println(node);
                return node;
            }
        }
    }

    /**
     * no对应的节点为叶子节点则删除节点；
     * 如果不是，那就删除子树。
     * @param no
     */
    public void delete(int no) {
        if (root.getNo() == no) {
            root = null;
        } else {
            root.delete(no);
        }
    }

    public void add(Node node){
        if (this.root==null) this.root = node;
        else {
            this.root.add(node);
        }
    }
}

class Node {
    private int no;
    private String msg;
    private Node left;
    private Node right;

    public Node(int no, String msg) {
        this.no = no;
        this.msg = msg;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", msg='" + msg + '\'' +
                '}';
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getMsg() {
        return msg;
    }

    public void setMsg(String msg) {
        this.msg = msg;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal() {

        System.out.println(this);

        if (this.left != null) this.left.preorderTraversal();
        if (this.right != null) this.right.preorderTraversal();
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        if (this.left != null) this.left.inorderTraversal();
        System.out.println(this);
        if (this.right != null) this.right.inorderTraversal();
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        if (this.left != null) this.left.postorderTraversal();
        if (this.right != null) this.right.postorderTraversal();
        System.out.println(this);
    }

    /**
     * 前序查找
     */
    public Node preorderSearch(int no) {

        if (this.no == no) return this;

        Node node = null;

        if (this.left != null) {
            node = this.left.preorderSearch(no);
        }

        if (node != null) {
            return node;
        }

        if (this.right != null) {
            node = this.right.preorderSearch(no);
        }

        return node;
    }


    /**
     * 中序查找
     */
    public Node inorderSearch(int no) {


        Node node = null;

        if (this.left != null) {
            node = this.left.inorderSearch(no);
        }

        if (node != null) {
            return node;
        }

        if (this.no == no) return this;

        if (this.right != null) {
            node = this.right.inorderSearch(no);
        }

        return node;
    }

    /**
     * 后续查找
     */
    public Node postorderSearch(int no) {


        Node node = null;

        if (this.left != null) {
            node = this.left.postorderSearch(no);
        }

        if (node != null) {
            return node;
        }

        if (this.right != null) {
            node = this.right.postorderSearch(no);
        }

        if (this.no == no) return this;

        return node;


    }


    public void delete(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delete(no);
        }
        if (this.right != null) {
            this.right.delete(no);
        }
    }

    public void add(Node node) {
        if (this.no>node.no) {
            if (this.left!=null) this.left.add(node);
            else {
                this.left=node;
                return;
            }
        }
        else {
            if (this.right!=null) this.right.add(node);
            else {
                this.right=node;
                return;
            }
        }
    }
}